package leetcode.p1049;

/**
 * 每次取两个石头相减，实际上等价于对一个序列加上正负号
 * @author: trtan
 * @date: 2021-06-08 08:44
 **/
public class LastStoneWeightTwo {
    public int lastStoneWeightII(int[] stones) {
        final int MAX_VALUE = 30 * 100;
        // dp[i][j] 代表前i个石头是否能凑成j的重量 因为每次都只和前一次有关，所以使用滚动数组
        boolean[][] dp = new boolean[2][MAX_VALUE + 5];
        int flag = 0;
        for (int i = 0; i < MAX_VALUE; i++) {
            if (i == 0) {
                dp[flag][i] = true;
            } else {
                dp[flag][i] = false;
            }
        }
        int sum = 0;
        for (int i = 1; i <= stones.length; i++) {
            // 0变1， 1变0
            int now_flag = Math.abs(flag - 1);
            sum += stones[i - 1];
            for (int j = 0; j <= MAX_VALUE; j++) {
                if (stones[i - 1] > j) {
                    dp[now_flag][j] = dp[flag][j];
                } else {
                    dp[now_flag][j] = (dp[flag][j] | dp[flag][j - stones[i - 1]]);
                }
            }
            flag = now_flag;
        }
        for (int i = sum / 2; i >= 0; i--) {
            if (dp[flag][i]) {
                return sum - 2 * i;
            }
        }
        return sum;
    }
}
